package com.ls.nodelist;

import java.util.HashSet;
import java.util.Set;

class Solution {

    public ListNode rotateRight(ListNode head, int k) {
        if(head == null){
            return null;
        }
        int count = 0;

        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            pre = cur;
            cur = cur.next;
            count ++;
        }
        pre.next = head;

        k = count - (k % count);

        cur = head;
        pre = null;
        while(k > 0){
            pre = cur;
            cur = cur.next;
            k--;
        }
        pre.next = null;

        return cur;
    }

    public void printNodeList(ListNode head){
        Set<ListNode> visted = new HashSet<>();
        while(head != null){
            if(visted.contains(head)){
                System.out.println("有循环链表");
                break;
            }
            visted.add(head);
            System.out.print(head.val + "->");
            head = head.next;
        }
        System.out.println();
    }

    /**
     * 328. 奇偶链表
     * @param head
     * @return
     */
    public ListNode oddEvenList(ListNode head) {
        if(head == null){
            return head;
        }

        ListNode cur = head;
        ListNode hone, htwo, curOne, curTwo, oneTail;
        hone = htwo = curOne = curTwo = oneTail = null;
        int count = 0;
        while(cur != null){
            count++;
            if(count % 2 == 0){
                if(curTwo == null){
                    htwo = cur;
                    curTwo = cur;
                }else{
                    curTwo.next = cur;
                    curTwo = cur;
                }
                cur = cur.next;
                curTwo.next = null;
            }else{
                if(curOne == null){
                    hone = cur;
                    curOne = cur;
                }else{
                    curOne.next = cur;
                    curOne = cur;
                }
                oneTail = cur;
                cur = cur.next;
                curOne.next = null;
            }
        }

        oneTail.next = htwo;
        return hone;
    }

    public ListNode oddEvenList2(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode evenHead = head.next;
        ListNode odd = head, even = evenHead;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }

    /**
     * 寻找链表的中间节点，偶数时返回中间的后一个
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head){
        ListNode fast, slow;
        fast = slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode node, head;
        node = head = new ListNode(1);
        node = node.next = new ListNode(2);
        node = node.next = new ListNode(3);
        node = node.next = new ListNode(4);
//        node = node.next = new ListNode(5);

        Solution s = new Solution();
//        ListNode listNode = s.rotateRight(head, 2);
//        ListNode listNode = s.oddEvenList(head);
//        s.printNodeList(listNode);
        ListNode listNode = s.middleNode(head);
        System.out.println(listNode.val);
    }

}

